The proliferation of networked computers and increased processor speeds in the workplace, at home and over the internet have increased the need by users on a computer network to concurrently access shared resources. Commonly, two processes will need to access a shared resource at the same time. This problem can arise, for example, when some users wish to read from a shared resource on a data storage device while another user is requesting permission to write to that shared resource. In another example, the problem can arise with respect to a shared resource on a standalone machine or on shared resources accessed across several networks. Though shared resources presently permit many users to obtain shared locks concurrently, several limitations to resource access can arise when one or more users wish to concurrently obtain an exclusive lock.
One such limitation is that shared lock requests and exclusive lock requests must be mutually exclusive. For example, if one process obtains a shared lock to read data and another process concurrently obtains an exclusive lock to write data to the same data segment, it is possible that the first process will read erroneous or outdated data. A practical illustration of this problem occurs when two remote members of a jointly held bank account wish to concurrently check the balance of their account and subsequently withdraw the reported balance via an automated teller machine. Without a data storage system that provides for mutual exclusivity, the joint account holders may overdraw the account if both members decide to withdraw the balance.
Shared resources that employ mutually exclusive shared and exclusive locks encounter the problems of starvation and deadlock, both of which are well known to those skilled in the art. Starvation occurs when a process that requests an exclusive lock on a shared resource is denied access to that shared resource in order to fulfill the requirement of mutual exclusivity (e.g., another process already owns a shared lock). Normally, starvation ends when existing shared locks on the shared resource complete their operations and release their locks. However, when other processes subsequently obtain multiple shared locks on the shared resource, the process requesting an exclusive lock will be starved from the shared resource for as long as any shared lock owners exist. Starvation is undesirable because it can delay critical system updates and is inefficient.
Deadlock occurs when, due to mutual exclusion, a set of processes are waiting on another process in the set to execute. For example, if the set is comprised of processes P0 through Pn wherein P0 is waiting on P1, P1 is waiting on P2, P2 is waiting on P3, . .and Pn is waiting on P0, a deadlock has occurred because no process in the set can execute until the process it is waiting for executes. For example, this problem occurs when a process with a shared lock requests a recursive lock after another process has already requested an exclusive lock. In this situation, the original shared lock is waiting on the recursive lock, the recursive lock is waiting on the exclusive lock, and the exclusive lock is waiting on the original shared lock. Deadlock is undesirable because it requires one process in the set to be manually aborted and is inefficient.
Thus, a need exists for computer networks to accommodate shared and exclusive lock requests while satisfying the requirement of mutual exclusivity and avoiding the problems of starvation and deadlock.
One response has been to account for the number of processes that hold shared locks on a particular shared resource. This solution defers exclusive lock requests so long as a process holds a shared lock on the resource. This solution is inadequate because it does not account for processes with recursive locks on the resource. In failing to differentiate between first-time and recursive lock requests, a process waiting for an exclusive lock can be starved if first-time lock requests are perpetually granted and a process waiting for a recursive lock can cause deadlock if its recursive lock request is deferred.
Another response has been to individually account for the number of shared locks held by each process for each particular shared resource. While shared locks exist, processes waiting to obtain an exclusive lock are queued and permitted to write only when all preceding processes have terminated their shared locks; all subsequent shared lock requests are put to sleep and granted only after preceding exclusive locks terminate. This solution is inadequate because it is computationally expensive and results in excessive overhead when the number of potential concurrent processes and the number of shared resources are considered.